package dp;

public class Solution416 {
    /**
     * 将问题转化为0-1背包问题
     * 假如我背包空间为sum/2，从前N个数中选择,每个数的需要的空间为nums[i]，能否恰好将我背包填满？
     * 思考状态与选择，状态依然是背包空间and可以选择的数字的范围
     * 选择就是选择装不装当前的数字
     *
     * 难点在于定义dp数组与写出状态转移方程
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        boolean b = knapsack(nums);
        return b;
    }


    public boolean knapsack(int[] nums){
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        //只有sum为偶数才有可能凑成题目要求
        if (sum % 2 != 0 ){
            return false;
        }

        int target = sum / 2;

        boolean[][]dp = new boolean[nums.length+1][target+1];
        //初始化dp数组
        /**
         * dp数组的定义为
         * 对于前 i 个物品（i 从 1 开始计数），当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，
         * 若 x 为 false，则说明不能恰好将背包装满。
         * 比如说，如果 dp[4][9] = true，其含义为：对于容量为 9 的背包，若只是在前 4 个物品中进行选择，可以有一种方法把背包恰好装满。
         */
        for (int i = 0;i< dp.length;i++){
            dp[i][0] = true;
        }

        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j]=false;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if ((j-nums[i-1])<0){
                    //第i个元素重量超过背包空间
                    //肯定不能选择加入
                    dp[i][j] = dp[i-1][j];
                }else {
                    /**
                     * 这个状态转移方程是怎么得出来的？
                     * 首先如果你选择不加入，那么直接用dp[i-1][j]
                     * 你选择加入的话，就得看看当前背包容量减去自己容量的那个容量下，选择前i-1个元素能否填满背包，他行你也行
                     */
                    dp[i][j] = (dp[i-1][j]||dp[i-1][j-nums[i-1]])==true ? true : false;
                }

            }
        }

        return dp[nums.length][target];
    }

    public static void main(String[] args) {
        int [] nums = new int[]{1,2,3,5};

        Solution416 solution416 = new Solution416();
        boolean could = solution416.canPartition(nums);

        System.out.println("could = " + could);
    }
}
